package Hot100;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2021-12-24 9:48
 */
public class merge56 {
    /** 56. 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，
     * 该数组需恰好覆盖输入中的所有区间。
     * 按照开始时间排序，然后找到重叠区间中的最大结束时间
    * */
    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        if (n==1) return intervals;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        LinkedList<int[]> list=new LinkedList<>();
        list.add(intervals[0]);
        for (int i = 1; i < n; i++) {
            int[] cur=intervals[i];
            int[] last = list.getLast();
            if (cur[0]<=last[1]){
                last[1]=Math.max(last[1],cur[1]);
            }else {
                list.add(cur);
            }
        }
        int[][] res=new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i]=list.get(i);
        }
        return res;
    }

    /**1288. 删除被覆盖区间
     * 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。在完成所有删除操作后，请你返回列表中剩余区间的数目。
     * 计算被覆盖区间，然后和总数相减得到结果。先按照开始时间排序，相同起点的按结束时间降序排列
     * 排序后相邻区间有三种情况：
     * 1、两个区间覆盖，由于终点降序排列，前一个区间覆盖后一个区间
     * 2、部分重叠，两个区间可以合并，成为一个大区间
     * 3、两个区间完全不相交
     * */
    public int removeCoveredIntervals(int[][] intervals) {
        int n=intervals.length;
        if (n==1) return intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }
                return o1[0]-o2[0];
            }
        });
        int res=0;
        //[left,right]记录前一个合并区间，后面的区间，只能和前一个合并
        int left=intervals[0][0],right=intervals[0][1];
        for (int i = 1; i < n; i++) {
            int[] cur=intervals[i];
            //1、两个区间覆盖，由于终点降序排列，前一个区间覆盖后一个区间
            if (cur[0]>=left&&cur[1]<=right){
                res++;
            }
            //2、部分重叠，两个区间可以合并，成为一个大区间
            if (cur[0]<=right&&cur[1]>=right){
                right=cur[1];
            }
            //3、两个区间完全不相交
            if (cur[0]>right){
                left=cur[0];
                right=cur[1];
            }
        }
        return n-res;
    }


    /**986. 区间列表的交集
     * 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。
     * 每个区间列表都是成对 不相交 的，并且 已经排序 。返回这 两个区间列表的交集 。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
     * 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
     * 双指针，判断两个区间的关系，交错前进，是否前进依据b2和a2的大小，哪个小，移动哪个
     * */
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int m=firstList.length,n=secondList.length;
        int i=0,j=0;
        LinkedList<int[]> list=new LinkedList<>();
        while (i<m&&j<n){
            int a1=firstList[i][0],a2=firstList[i][1];
            int b1=secondList[j][0],b2=secondList[j][1];
            //判断两个区间是否有交集
            if (a1<=b2&&a2>=b1){
                list.add(new int[]{Math.max(a1,b1),Math.min(a2,b2)});
            }
            if (a2<=b2){
                i++;
            }else {
                j++;
            }
        }
        int[][] res=new int[list.size()][2];
        for (int k = 0; k < list.size(); k++) {
            res[k]=list.get(k);
        }
        return res;
    }

    public static void main(String[] args) {
        merge56 obj=new merge56();
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        //System.out.println(obj.merge(intervals));
        int[][] firstList = {{0,2},{5,10},{13,23},{24,25}};
        int[][] secondList = {{1,5},{8,12},{15,24},{25,26}};
        System.out.println(obj.intervalIntersection(firstList,secondList));
    }
}
